#include "makefile_deps.h"

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <list>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>

#include <time.h>

#include "fast_build_helper.h"

using std::list;
using std::vector;
using std::cout;
using std::endl;

void printDeps(map<string, Deps*> &deps);
void printDepsChildren(Deps* deps);
void printLeaf(vector<Deps*> &deps);
void addToLeafList(vector<Deps*> &leaf_list, map<string, Deps*> &leaf_map,
    STRATEGY strategy);
bool insertToDeps(Deps*& target, Deps*& deps);
void printLevelCount(vector<int> &level_count, vector<int> &bits_level);
bool depsLessThan(Deps* lhs, Deps* rhs);
bool depsPriorityComparator(Deps* lhs, Deps* rhs);
void setTmpExecTime(map<string, Deps*> &deps_map);
void setBits(char *priority_bits, unsigned int value, int shift);

MakefileDeps::MakefileDeps() : deps_graph_(NULL) {
}

MakefileDeps::MakefileDeps(char* make_file) : make_file_(make_file),
    deps_graph_(NULL) {
}

MakefileDeps::MakefileDeps(char* make_file, char* cc_filename,
    char* link_filename) : make_file_(make_file),
    cc_time_filename_(cc_filename), link_time_filename_(link_filename),
    deps_graph_(NULL), num_bits_level_(1), total_deps_(0),
    max_parallelism_(0) {
}

MakefileDeps::~MakefileDeps() {
  pthread_mutex_destroy(&(this->leaf_list_lock_));
}

/**
* Initializes the dependency tree
*/
void MakefileDeps::Initialize() {

  srand(time(NULL));
  pthread_mutex_init(&(this->leaf_list_lock_), NULL);
  ConstructDependencyGraph(make_file_);
  // Set the total size of dependency nodes in the graph
  total_deps_ = deps_map_.size();

  AddLevelCount();
  printLevelCount(num_child_level_, num_bits_level_);
  cout << "Total deps " << deps_map_.size() << endl;

  SetExecutionTime(cc_time_filename_);
  SetExecutionTime(link_time_filename_);
  SetHeuristics();

  AssignPriorities();

  // After assigning the priorities construct the heap
  addToLeafList(leaf_deps_, leaf_deps_map_, strategy_);
  max_parallelism_ = leaf_deps_.size();

//  printDeps(deps_map_);
//  printLeaf(leaf_deps_);
}


/**
* Constructs the dependecy tree from the given pre-processed Makefile
*
* @Param filename
*/
void MakefileDeps::ConstructDependencyGraph(char* filename) {
  cout << "Constructing deps graph from " << filename << endl;
  FILE *file = fopen(filename, "r");
  if (file == NULL) {
    cout << "File does not exist " << filename << endl;
    exit(-1);
  }

  char str[1000];
  char target_str[1000];
  char deps_str[1000];

  fgets(str, 1000, file);

  // The input is of the form target1 : deps1 \n target1 : deps2
  while (strstr(str, "EOF") == NULL) {
    sscanf(str, "%s %s", target_str, deps_str);
    AddDependency(string(target_str), string(deps_str), deps_map_);
    fgets(str, 1000, file);
  }
  fclose(file);
}

void MakefileDeps::SetExecutionTime(char* compile_time_file) {
  FILE *file = fopen(compile_time_file, "r");
  if (file == NULL) {
    cout << "File does not exist " << compile_time_file << endl;
    exit(-1);
  }

  char str[1000];
  char file_str[1000];
  double cc_time;
  double t1;
  double t2;

  fgets(str, 1000, file);
  int counter = 0;

  // The input is of the form target1 : deps1 \n target1 : deps2
  while (strstr(str, "EOF") == NULL) {
    sscanf(str, "%s %lf %lf %lf", file_str, &cc_time, &t1, &t2);
    string file_string(file_str);
    if (deps_map_.count(file_string) > 0) {
      deps_map_[file_string]->set_heuristic_time(cc_time);
      deps_map_[file_string]->set_exec_time(cc_time);
    } else {
      counter++;
    }
    fgets(str, 1000, file);
  }
  cout << counter << " files not found in deps " << endl;
  fclose(file);
}

/**
* Adds to the dependency tree the specified target and dependency
*
* @Param target_str target of the rule
* @Param deps_str dependency of the rule
* @Param deps_map_ map storing the pointer to Deps for each file_name
*/
void MakefileDeps::AddDependency(string target_str, string deps_str, map<string,
    Deps*> &deps_map_) {
  Deps* target;
  Deps* deps;

  // If the target deps does not exist, create a new one and insert it into the
  // map
  if (deps_map_.count(target_str) == 0) {
    long fsize = build_helper::GetFileSize(target_str.c_str());
    target = new Deps(target_str, fsize);
    target->RegisterObserver(this);
    deps_map_[target_str] = target;
    topmost_deps_map_[target_str] =target;
  } else {
    // Retrieve the Deps node pointer from the map
    target = deps_map_[target_str];
    if (leaf_deps_map_.count(target_str) > 0) {
      leaf_deps_map_.erase(target_str);
    }
  }

  if (deps_map_.count(deps_str) == 0) {
    long fsize = build_helper::GetFileSize(deps_str.c_str());
    deps = new Deps(deps_str, fsize);
    deps->RegisterObserver(this);
    deps_map_[deps_str] = deps;
    leaf_deps_map_[deps_str] = deps;
  } else {
    deps = deps_map_[deps_str];
  }

  if (topmost_deps_map_.count(deps_str) > 0) {
    topmost_deps_map_.erase(deps_str);
  }

  if (leaf_deps_map_.count(target_str) > 0) {
    topmost_deps_map_.erase(target_str);
  }

  // Add the new dependency to the target file
  insertToDeps(target, deps);

  // Register the target as an observer of deps node so that the deps can notify
  // the target (parent) whenever its state changes.
  deps->RegisterObserver(target);
}

void MakefileDeps::SetHeuristics() {
  map<string, Deps*>::iterator it;
  for (it = topmost_deps_map_.begin(); it != topmost_deps_map_.end(); it++) {

    // Call AssignPriorities on its children which is the dependencies
    SetHeuristics(it->second);
  }
}

/**
* Set the time heuristics for each node in the dependency graph
*
* @Param deps
*/
void MakefileDeps::SetHeuristics(Deps* deps) {
  if (deps == NULL) {
    return;
  }


  double max_child_time = 0;

  // Find the child which has the maximum heuristic time. This is a
  // recursive call since its heuristic time would be dependent on its children.
  vector<Deps*> deps_dependencies = deps->dependencies_;

  for (int i = 0; i < deps_dependencies.size(); i++) {
    SetHeuristics(deps_dependencies[i]);

    // If the time is greater than the current max and the child hasn't finished
    // its execution, then consider it to be the maximum time.
    if (deps_dependencies[i]->heuristic_time() > max_child_time &&
        !deps_dependencies[i]->execution_done()) {
      max_child_time = deps_dependencies[i]->heuristic_time();
    }
  }
  double self_time = deps->heuristic_time();
  deps->set_heuristic_time(self_time + max_child_time);
}

void printLeaf(vector<Deps*> &deps) {
  cout << "Leaf Jobs : " << deps.size() << endl;
  for (int i = 0; i < deps.size(); i++) {
    cout << i << ". " << deps[i]->filename().c_str() << " priority " <<
        deps[i]->priority() << endl;
  }
}

void printDeps(map<string, Deps*> &deps) {
  int count = 1;
  map<string, Deps*>::iterator it;
  for (it = deps.begin(); it != deps.end(); it++, count++) {
    cout << count  << ". " << it->first << " : " <<
      it->second->filesize()
      << "\tpriority : " << it->second->priority() <<
      "\theuristic time : " << it->second->heuristic_time() <<
      "\texec time : " << it->second->exec_time() << 
      endl;
    printDepsChildren(it->second);
  }
}

void printDepsChildren(Deps* deps) {
  vector<Deps*> deps_deps = deps->dependencies_;
  for (int i = 0; i < deps_deps.size(); i++) {
    cout << "\t" << deps_deps[i]->filename() << endl;
  }
}

bool insertToDeps(Deps*& target, Deps*& deps) {
  vector<Deps*> target_deps = target->dependencies_;
  for (int i = 0; i < target_deps.size(); i++) {
    if (target_deps[i] == deps) {
      return false;
    }
  }

  target->dependencies_.push_back(deps);
  return true;
}

Deps* MakefileDeps::GetDependencyGraph() {
  return deps_graph_;
}

void MakefileDeps::Update(UpdateInfo update_info) {
  int update_type = update_info.update_type_;
  Deps* update_from_deps = (Deps *) update_info.from_subj_;

  switch (update_type) {

    // If the update is for Scheduling, then add this deps to the leaf list
    case UpdateInfo::SCHEDULE:
      AddToLeafList(update_from_deps);
      cout << "Scheduling new job " << update_from_deps->filename() << endl;
      break;

      // If this update is saying Completed, then remove this deps from the leaf
      // list
    case UpdateInfo::COMPLETED:
      time_t raw_time;
      time(&raw_time);
      cout <<"Completed job : " << update_from_deps->filename() <<
          " time: " << ctime(&raw_time) << endl;
      break;

    default:
      cout << "Not handled " << endl;
  }
}

/**
* Depending on the strategy, a Deps node is returned to the scheduler
*
* @Returns   
*/
Deps* MakefileDeps::GetNextLeafToSchedule() {
  Deps* deps = NULL;
  int leaf_index;
  switch (strategy_) {
    case RANDOM :
      deps = RemoveRandomLeaf();
      break;

    case PRIORITY :
     // cout << "Removing from max heap " <<endl;
      deps = RemoveFromMaxLeafHeap();
      break;

    default : 
      cout << "ERROR : Strategy is not set " << endl;
  }
  return deps;
}

/**
* Remove a random leaf from the list of leaf_deps_ list
*
* @Returns  a pointer to the Deps node. If there are no nodes, then returns NULL 
*/
Deps* MakefileDeps::RemoveRandomLeaf() {
  Deps* deps = NULL;
  pthread_mutex_lock(&leaf_list_lock_);
  if (leaf_deps_.size() != 0) {
    int leaf_index = rand() % leaf_deps_.size();
    deps = leaf_deps_[leaf_index];
    leaf_deps_.erase(leaf_deps_.begin() + leaf_index);
  }
  pthread_mutex_unlock(&leaf_list_lock_);
  return deps;
}

/**
 * Remove the given deps from the leaf_deps list
 *
 * @Param deps
 */
void MakefileDeps::RemoveFromLeafList(Deps* deps) {
  for (int i = 0; i < leaf_deps_.size(); i++) {
    if (leaf_deps_[i] == deps) {
      leaf_deps_.erase(leaf_deps_.begin() + i);
    }
  }
}

/**
 * This returns the Deps node from the max heap of leaves.
 *
 * @Returns NULL if there are no nodes in the heap
 */
Deps* MakefileDeps::RemoveFromMaxLeafHeap() {
  pthread_mutex_lock(&leaf_list_lock_);
  Deps* deps = NULL;
  if (leaf_deps_.size() != 0) {
    deps = leaf_deps_.front();
    pop_heap(leaf_deps_.begin(), leaf_deps_.end(), depsPriorityComparator);
    leaf_deps_.pop_back();
  }
  pthread_mutex_unlock(&leaf_list_lock_);
  return deps;
}

/**
 * Add to the leaf list the deps passed in
 *
 * @Param deps
 */
void MakefileDeps::AddToLeafList(Deps* deps) {
  switch (strategy_) {
    case RANDOM :
      pthread_mutex_lock(&leaf_list_lock_);
      leaf_deps_.push_back(deps);
      if (max_parallelism_ < leaf_deps_.size()) {
        max_parallelism_ = leaf_deps_.size();
      }
      pthread_mutex_unlock(&leaf_list_lock_);
      break;

    case PRIORITY :
      pthread_mutex_lock(&leaf_list_lock_);
      leaf_deps_.push_back(deps);
      if (max_parallelism_ < leaf_deps_.size()) {
        max_parallelism_ = leaf_deps_.size();
      }
      push_heap(leaf_deps_.begin(), leaf_deps_.end(), depsPriorityComparator);
      pthread_mutex_unlock(&leaf_list_lock_);
      break;

    default : 
      cout << "ERROR : Strategy is not set " << endl;
  }
}

void printLevelCount(vector<int> &level_count, vector<int> &bits_level) {
  int counter = 0;
  int total_bits = 0;
  for (int i = 0; i < level_count.size(); i++) {
    counter += level_count[i];
    total_bits += bits_level[i];
    cout << "Level [" << i << "] : " << level_count[i] << " bits : " <<
      bits_level[i] << endl;
  }
  cout << " Level count total " << counter << " total bits: " << total_bits << endl;
}

/**
 * This is a helper for setting priority bits
 */
void MakefileDeps::AddLevelCount() {
  int level = 0;
  num_child_level_.resize(level + 1);
  num_child_level_[level] = topmost_deps_map_.size();

  map<string, Deps*>::iterator it;
  for (it = topmost_deps_map_.begin(); it != topmost_deps_map_.end(); it++) {
    AddLevelCount(it->second, level + 1);
  }

  num_bits_level_.resize(num_child_level_.size());
  total_bits_ = 0;
  for (int i = 0; i < num_child_level_.size(); i++) {
    if (num_child_level_[i] != 1) {
      num_bits_level_[i] = ceil (log2(num_child_level_[i]));
    } else {
      num_bits_level_[i] = 1;
    }
    total_bits_ += num_bits_level_[i];
  }
}

void MakefileDeps::AddLevelCount(Deps* deps, int level) {
  if (deps != NULL && (deps->dependencies_.size() != 0)) {
    if (num_child_level_.size() <= level) {
      num_child_level_.resize(level + 1);
    }
  }

  vector<Deps*> deps_dependencies = deps->dependencies_;
  for (int i = 0; i < deps_dependencies.size(); i++) {
    num_child_level_[level]++;
    AddLevelCount(deps_dependencies[i], level+1);
  }
}

void MakefileDeps::AssignPriorities() {
  // Sort the topmost levels and set its priority.
  vector<Deps*> topmost_deps;
  map<string, Deps*>::iterator it;
  for (it = topmost_deps_map_.begin(); it != topmost_deps_map_.end(); it++) {
    topmost_deps.push_back(it->second);
  }

  sort(topmost_deps.begin(), topmost_deps.end(), depsLessThan);
  Deps *deps;
  int no_of_child = 0;
  int level = 0;
  if (topmost_deps.size() == 1) {
    no_of_child = 1;
  } else if (topmost_deps.size() != 0) {
    no_of_child = ceil (log2(topmost_deps.size()));
  }
  for (unsigned int i = 0; i < topmost_deps.size(); i++) {

    deps = topmost_deps[i];


  //  char prio_bits[no_of_child + 1];
  //  prio_bits[no_of_child] = '\0';
  //  setBits(prio_bits, i, no_of_child);
    char prio_bits[num_bits_level_[level] + 1];
    prio_bits[num_bits_level_[level]] = '\0';
    setBits(prio_bits, i, num_bits_level_[level]);

    string new_priority(prio_bits);
    deps->set_priority(new_priority);

    // Call AssignPriorities on its children which is the dependencies
    AssignPriorities(deps->dependencies_, new_priority, level + 1);
  }
}

void MakefileDeps::AssignPriorities(vector<Deps*> deps_children,
    string parent_priority, int level) {
  if (deps_children.size() == 0) {
    return;
  }
  sort(deps_children.begin(), deps_children.end(), depsLessThan);

  int no_of_child = 0;
  if (deps_children.size() == 1) {
    no_of_child = 1;
  } else if (deps_children.size() != 0) {
    no_of_child = ceil (log2(deps_children.size()));
  }

  for (unsigned int i = 0; i < deps_children.size(); i++) {
   // char prio_bits[no_of_child + 1];
   // prio_bits[no_of_child] = '\0';
   // setBits(prio_bits, i, no_of_child);

    char prio_bits[num_bits_level_[level] + 1];
    prio_bits[num_bits_level_[level]] = '\0';
    setBits(prio_bits, i, num_bits_level_[level]);
    string new_priority(parent_priority);
    new_priority.append(prio_bits);

    if (deps_children[i]->priority() < new_priority) {
      deps_children[i]->set_priority(new_priority);
      AssignPriorities(deps_children[i]->dependencies_, new_priority, level+1);
    }
  }
}

void setBits(char *priority_bits, unsigned int value, int shift) {
  const unsigned mask = 1 << (shift - 1);
  for (int i = 0; i < shift; i++) {
    priority_bits[i] = (value & mask ? '1' : '0');
    value <<= 1;
  }
}


bool depsLessThan(Deps* lhs, Deps* rhs) {
  return (lhs->heuristic_time() < rhs->heuristic_time()) ? true : false;
}

bool depsPriorityComparator(Deps* lhs, Deps* rhs) {
  return (lhs->priority() < rhs->priority()) ? true : false;
}

void addToLeafList(vector<Deps*> &leaf_list, map<string, Deps*> &leaf_map,
    STRATEGY strategy) {
  map<string, Deps*>::iterator it;
  for (it = leaf_map.begin(); it != leaf_map.end(); it++) {
    leaf_list.push_back(it->second);
  }

  switch (strategy) {
    case RANDOM :
      break;

    case PRIORITY :
      make_heap(leaf_list.begin(), leaf_list.end(), depsPriorityComparator);
      break;

    default : 
      cout << "ERROR : Strategy is not set " << endl;
  }
}

void setTmpExecTime(map<string, Deps*> &deps_map) {
  map<string, Deps*>::iterator it;
  for (it = deps_map.begin(); it != deps_map.end(); it++) {
    it->second->set_exec_time(rand() % 10 + 1);
  }
}
